package com.tgy.algorithm._经典题目01;

/**
 *
 * 有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。
 * 现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将会被覆盖。
 * 目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。
 * 返回最少需要涂染几个正方形。
 * 如样例所示:s=RGRGR 我们涂染之后变成RRRGG满足要求了,
 * 涂染的个数为2没有比这个更好的涂染方案。
 */
public class _004_正方形染色 {

    public static int minDye(String content) {
        if (content == null || content.length() == 0 || content.length() == 1) {
            return 0;
        }

        int len = content.length();
        char[] chars = content.toCharArray();
        int[] leftNums = new int[len + 1];
        int[] rightNums = new int[len + 1];

        for (int i = 1; i <= len; i++) {
            char aChar = chars[i - 1];
            char lastChar = chars[len - i];
            leftNums[i] = leftNums[i - 1];
            if (aChar == 'G') {
                leftNums[i]++;
            }

            rightNums[len - i] = rightNums[len - i + 1];
            if (lastChar == 'R') {
                rightNums[len - i]++;
            }
        }

        int minLen = Integer.MAX_VALUE;

        for (int i = 0; i < len + 1; i++) {
            minLen = Math.min(minLen,leftNums[i] + rightNums[i]);
        }

        return minLen;
    }

    public static void main(String[] args) {
        String content = "RGRGR";
        int min = minDye(content);
        System.out.println(min);
    }
}
